package com.mashibing.class04;

// 测试链接：https://leetcode.com/problems/add-two-numbers/
public class Code05_AddTwoNumbers {
    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
        int len1 = listLength(head1);
        int len2 = listLength(head2);
        // 将较长的链表和较短的链表分别保存在 l和s 中. 长短链表重定向.
        ListNode l = len1 >= len2 ? head1 : head2;
        ListNode s = l == head1 ? head2 : head1;
        // curL 和 curS 用来记录长连接和短连接的遍历计算节点.
        ListNode curL = l;
        ListNode curS = s;
        // last 记录尾节点, 主要是为了挂载新的进位节点挂载在哪里.
        ListNode last = curL;
        int carry = 0;
        int curNum = 0;
        while (curS != null) {
            // 长链表 + 短链表 + 进位值
            curNum = curL.val + curS.val + carry;
            // 取出数据的个位值
            curL.val = (curNum % 10);
            // 记录进位值
            carry = curNum / 10;
            // 记录长链表的当前遍历节点.
            last = curL;
            // 长链表和短链表一起往前走
            curL = curL.next;
            curS = curS.next;
        }
        // 短链表结束, 长链表未结束.
        while (curL != null) {
            curNum = curL.val + carry;
            curL.val = (curNum % 10);
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
        }
        // 长短链表都结束之后的处理.
        if (carry != 0) {
            last.next = new ListNode(1);
        }
        return l;
    }

    // 求链表长度
    public static int listLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}
